import math
for i in range(int(input())):
n=int(input())
values=list(map(int,input().split()))
values2=[]
for k in range(1001):
values2.append([0])
l=0
while l<n:
values2[values[l]].append(l+1)
values2[values[l]][0]+=1
l+=1
values1=[]
value=[0]*1001
for val in values:
value[val]+=1
g=0
while g<1001:
if value[g]>0:
values1.append(g)
g+=1
le=len(values1)
j=0
flag=0
ma=0
curr=[]
nxt=[]
b=0
while j<le :
k=j
while k<le:
if math.gcd(values1[j],values1[k])==1:
curr.append(values1[j])
nxt.append(values1[k])
b+=1
flag=1
k+=1
j += 1
if flag==0:
print(-1)
else:
c=0
while c<b:
ch1=values2[curr[c]][0]
ch2=values2[nxt[c]][0]
ma=max(ma,values2[curr[c]][ch1]+values2[nxt[c]][ch2])
c+=1
print(ma)
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long t;
cin>>t;
while(t--)
{
long long n;
cin>>n;
vector<int> a(1001);
for(int i=1;i<=n;i++)
{
int temp;
cin>>temp;
a[temp]=i;
}
long long max= -1;
for(long long i=1;i<=1000;i++)
{
for(long long j=1;j<=1000;j++)
{
if(a[i] && a[j] && ((int)__gcd(i,j)==1))
{
if(max<(a[i]+a[j]))
{
max=a[i]+a[j];
}
}
}
}
cout<<max<<endl;
}
}1108B - Divisors of Two Integers | 1175A - From Hero to Zero |
1141A - Game 23 | 1401B - Ternary Sequence |
598A - Tricky Sum | 519A - A and B and Chess |
725B - Food on the Plane | 154B - Colliders |
127B - Canvas Frames | 107B - Basketball Team |
245A - System Administrator | 698A - Vacations |
1216B - Shooting | 368B - Sereja and Suffixes |
1665C - Tree Infection | 1665D - GCD Guess |
29A - Spit Problem | 1097B - Petr and a Combination Lock |
92A - Chips | 1665B - Array Cloning Technique |
1665A - GCD vs LCM | 118D - Caesar's Legions |
1598A - Computer Game | 1605A - AM Deviation |
1461A - String Generation | 1585B - Array Eversion |
1661C - Water the Trees | 1459A - Red-Blue Shuffle |
1661B - Getting Zero | 1661A - Array Balancing |